Access control mechanisms may apply (possibly user-defined) policies to determine who is allowed to access which resources in what manner. Access control mechanisms are widely applied in distributed systems such as (possibly SOA-based) web services.
Different languages exist for specifying policies. One of said programming and/or modeling language is the eXtensible Access Control Markup Language (XACML). XACML is an XML-based language standardized by OASIS in 2003. XACML has been widely supported by a plurality of platform vendors and extensively used in a variety of applications.
Evaluation engines may be implemented to enforce a policy. One example is Sun XACML PDP, which is an implementation of XACML evaluation engines. Sun XACML PDP is widely deployed for web services and/or web applications, in particular Java-based applications.
In order to evaluate a request to a resource protected by a policy, the Sun XACML PDP may perform a linear searching by comparing the request with one or more or even all rules in the policy sequentially. Consequently, when modeling the policy as a tree, the Sun XACML PDP may perform a depth first search (i.e. a search by applying a depth first traverse) to find the proper rule to evaluate the policy according to the request. Thus, for a certain group of requests, if more rules in the last part of the policy are evaluated, a performance of the evaluation engine may be low.